package com.shigi.knapsack.solvers;

import com.shigi.knapsack.KnapsackInstance;
import com.shigi.knapsack.KnapsackItem;
import com.shigi.knapsack.KnapsackSolution;
import com.shigi.knapsack.KnapsackSolver;

/**
 * Created by Miroslav Šiagi on 27/09/14.
 */
public class BruteForce implements KnapsackSolver {

    private KnapsackSolution knapsackSolution;
    private KnapsackInstance knapsackInstance;
    private KnapsackItem[] knapsackItems;

    public KnapsackSolution solve(KnapsackInstance knapsackInstance) {
        this.knapsackInstance = knapsackInstance;
        this.knapsackSolution = new KnapsackSolution(knapsackInstance.getId());
        this.knapsackSolution.setNumberOfItems(knapsackInstance.getNumberOfItems());
        this.knapsackItems = this.knapsackInstance.getKnapsackItems();

        int usedItems = 0;
        double upperLimit = Math.pow(2.0, (double)knapsackInstance.getNumberOfItems());
        int tmpMaxValue = -1;
        for(int i = 0; i < upperLimit; i++) {
            int newValue = getValue(i);
            if(newValue >= tmpMaxValue) {
                tmpMaxValue = newValue;
                usedItems = i;
            }
        }

        knapsackSolution.setTotalValue(tmpMaxValue);
        knapsackSolution.setUsedItems(usedItems);
        return knapsackSolution;
    }


    private int getValue(int currentItems) {
        int value = 0;
        int totalWeight = 0;

        int rest = currentItems;
        int iterator = this.knapsackInstance.getNumberOfItems() - 1;
        while(rest > 0) {
            int isThere = rest % 2;
            value += isThere * this.knapsackItems[iterator].getValue(); //valueWeightPairs[iterator].getValue();
            totalWeight += isThere * this.knapsackItems[iterator].getWeight(); //valueWeightPairs[iterator].getKey();
            rest = rest / 2;
            iterator--;
        }

        if(totalWeight > this.knapsackInstance.getTotalWeight()) {
            return -1;
        } else {
            return value;
        }
    }


}
